import java.util.Stack;
//739. 每日温度
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();
        int[] answer = new int[temperatures.length];
        for(int i=0;i<temperatures.length;i++){
            int curNum = temperatures[i];
            while(!stack.isEmpty()&&temperatures[stack.peek()]<curNum){
                int prev = stack.pop();
                answer[prev] = i - prev;
            }
            stack.push(i);
        }
        return answer;
    }
}


//84. 柱状图中最大的矩形
class Solution1 {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) return 0;

        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int n = heights.length;

        for (int i = 0; i <= n; i++) {
            // 当前柱子的高度（如果 i == n，则视为高度 0，强制弹出所有剩余柱子）
            int currHeight = (i == n) ? 0 : heights[i];

            // 如果当前柱子比栈顶柱子矮，则计算栈顶柱子的最大矩形面积
            while (!stack.isEmpty() && currHeight < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                // 宽度 = 当前索引 i - 新的栈顶索引 - 1（如果栈为空，则宽度就是 i）
                int width = stack.isEmpty() ? i : (i - stack.peek() - 1);
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i); // 当前柱子入栈
        }

        return maxArea;
    }
}